package main

import "fmt"

/*
*
Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

利用快慢指针

循环查找
当fast.Forward==nil 或者fast=slow时跳出循环
为什么不能一个指针不动 另一个指针单步走来检查呢?
![20180810153384179440826.png](http://cdn.bsummer.cn/20180810153384179440826.png)
*/
type ListNode struct {
	Val  int
	Next *ListNode
}

func main() {

	a := ListNode{Val: 1, Next: nil}
	b := ListNode{Val: 2, Next: nil}
	c := ListNode{Val: 3, Next: nil}
	a.Next = &b
	b.Next = &c
	c.Next = &a

	fmt.Println(hasCycle(&a))
}

func hasCycle(head *ListNode) bool {
	if head == nil {
		return false
	}

	fast := head
	slow := head
	for fast != nil && fast.Next != nil && slow != nil {
		slow = slow.Next
		fast = fast.Next.Next

		if fast == slow {
			return true
		}
	}
	return false
}
